package BackTracking.subset;//给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
//
// 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。 
//
// 
// 
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,2,2]
//输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
// 
//
// 示例 2： 
//
// 
//输入：nums = [0]
//输出：[[],[0]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 10 
// -10 <= nums[i] <= 10 
// 
// 
// 
// Related Topics 位运算 数组 回溯 👍 690 👎 0
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class subsetsWithDup {

    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        int len = nums.length;
        if (len==0){
            res.add(new ArrayList<>(path));
            return res;
        }
        /**
         * 回溯遇到这种数组中有重复元素，但结果要求不重复，就先排序
         * 在回溯时，就要避免遇到和已经回溯相同的值，遇到了就跳过
         * */
        Arrays.sort(nums);
        sub(nums,0,len);
        return res;

    }

    private void sub(int[] nums, int start, int n){
        res.add(new ArrayList<>(path));
        if(start >= n){
            return;
        }
        for (int i = start; i < n; i++) {
            if(i>start && nums[i] == nums[i-1]){
                continue;
            }
            path.add(nums[i]);
            sub(nums, i+1, n);
            path.remove(path.size()-1);
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)
